package com.algorithm.learning.base;

/**
 * @program: algorithm-learning
 * @description: 现在有一个需求，给一个数组，可能会经常查询L~R位置的累加和
 *               例如：给定一个数组arr[0,1,2,3,4,5,6]，那么经常要获取index 0~2的元素累加和，或者 3~6的元素累加和
 *
 *               怎么处理
 * @author: YuKai Fan
 * @create: 2024/8/19 22:01
 **/
public class 经常查询某些位置的累加和 {

    /**
     * 对于这个需求，有三种方案解决。
     *
     * 1、暴力遍历求和，每次都从头开始遍历，直到遍历的L~R位置的元素进行累加和，效率比较低，每次都要遍历
     *
     * 2、构建一个二维数组，二维数组中合理的位置就作为元素的累加和，比如：arr = [2,5,3,1,6,7,4]
     *      0    1      2      3       4        5       6
     * 0    2  5+2=7 3+7=11 1+11=12  12+6=18  18+7=25  25+4=29
     * 1    x   5    5+3=8  8+1=9    9+6=15   15+7=22  22+4=26
     * 2    x   x      3    3+1=4    4+6=10   10+7=17  17+4=21
     * 3    x   x      x      1      1+6=7     7+7=14  14+4=18
     * 4    x   x      x      x        6       6+7=13  13+4=17
     * 5    x   x      x      x        x         7      7+4=11
     * 6    x   x      x      x        x         x         x
     *
     * 那么我要获取任意L~R位置的累加和，只需要在二维数组中找到对应的坐标即可。
     * 但是很明显这样做的缺点就是，我首先要构建一个二维数组，这个二维数组的大小是 (arr.length * arr.length)/2，那么如果数组长度很大，那么构建的二维数组也非常大，而且很耗时
     *
     * 3、我们依然可以构建一个一维数组help[]，这个一维数组就是存着，0-0累加和, 0-1累加和，0-2的累加和。。。。0-i的累加和。
     *      比如：help = [2, 7, 10, 11, 17, 24, 28]。那么根据help数组，首先我可以获取任意0-i位置的累加和。即help[i]
     * 如果要获取L~R位置的累加和，L>0 & L<R, 那么也只需要，help[R] - help[L-1] 即可。
     *      比如，要获取3-6位置的累加和，那么help[6] - help[2] = 28 - 10 = 18。
     *      因为help[6] = arr[0] +... +arr[6], help[2] = arr[0] + arr[1] +arr[2]
     *      help[6] - help[2] = arr[3] + ... +arr[6];
     */
    public static class NumPreSum {
        private final int[] preSum;

        public NumPreSum(int[] arr) {
            preSum = new int[arr.length];
            preSum[0] = arr[0];
            for (int i = 1; i < arr.length; i++) {
                preSum[i] = preSum[i - 1] + arr[i];
            }
        }

        public int getSum(int L, int R) {
            // 如果L==0，那么就直接获取R位置数即可
            return L > 0 ? preSum[R] - preSum[L - 1] : preSum[R];
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 1, 6, 7, 4};
        System.out.println(new NumPreSum(arr).getSum(3, 6));
    }
    
    
}
